HW#3 --- last modified February 10 2019 21:57:21..

Solution set.

Due date: Oct 31

Files to be submitted:
  Hw3.zip

Purpose:To gain experience with diagonalization techniques. To learn more about completeness techniques.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO3 -- Show the completeness of a complete problem for each of these classes.

LO8 -- Exhibit a relativized separation (oracle result) of complexity classes for standard classes such as P and NP.

Specification:

This homework consists in doing the following problems:

1. Prove the general case of the deterministic time hierarchy theorem presented in class.
2. Prove the definition of H(n) in Ladner's theorem implies an `O(n^3)`-time algorithm to compute `H(n)` from `n`.
3. Imagine that we expand the definition of CNF to include clauses of the form `A(x_1, ..., x_n)` for some language `A`. This clause is true if under a variable assignment the string represented by `x_1 ...x_n` is in the language `A`. Let `SAT^A` denote the problem of determining if a set of CNF clauses expanded with `A` clauses is satisfiable. Prove this problem is `NP^A`-complete. Show there exists an `A` such that `SAT^A` is not in `P^A`.
4. Show that 2SAT is in NL.
5. Show that `TQBF_k` (the problem of determining if a `k`-alternation quantified boolean formula with outermost existential `exists` is true) is `Sigma_k^p`-complete under logspace reductions. Show `TQBF` is PSPACE-complete under logspace reductions.

On the day your homework is due I will ask each group to present one problem to me in class.

If you scored above 8 on Hw2 and you work for Hw3 with someone who scored below 8 on Hw2, I will give you a 1pt bonus. Similarly, if you scored below 8 on Hw2 and you work for Hw3 with someone who scored above 8 on Hw2, I will give you a 1pt bonus. Be advised though that all group members must be prepared to answer any question on class presentation day.

Point Breakdown